/**
 * 不使用递归，实现树的后序遍历
 * 1.沿着根的左孩子入栈，直到左孩子为空，
 * 2.读取栈顶的元素，如果他的右孩子不为空且没有被访问过，那么就对有孩子执行1，否则访问栈顶元素并出栈
 * 在第二部中，必须分清返回的时左子树还是右子树，要设置一个辅助指针，指向最近访问的节点，也可以在节点中增加一个访问标志，标记是否被访问过了
 */
#include"BiTree.h"
#include"../stack/stack.h"//这个stack不合适，先这样用着
void post(BiTree *t){
    SqStack *s;
    initStack(s);
    BiTree *p=t;
    BiTree *r=nullptr;
    while (p||!stackEmpty(s))//p不为空，或者栈不为空
    {
        if(p){//p不为空，就将p放入栈，然后找左子树
            pushStack(s,p);
            p=p->left;
        }else{//p为空，说明左子树到头了，将栈弹出一个，看左边的那个叶子节点是否有右子树
            getTopStack(s,p);//这里仅仅读这个节点，看一看他有没有右子树，并没有弹出和访问
            if(p->right&&p->right!=r){//如果有右子树且右子树没有被访问过
                p=p->right;//转向右子树（下一轮循环中，会将这个节点pushStack
            }else{//否则弹出这个节点，然后访问
                popStack(s,p);
                visit(p->val);
                r=p;//记录最近访问过的节点
                //每次访问一个节点，就相当于遍历完了以这个节点为根的子树，所以要将p置为null
                p=nullptr;//节点访问过后，重置p指针
            }
        }
    }

    
}

